We study two types of two player, perfect information games with no chancemoves, played on the edge set of the binomial random graph ${\mathcal G}(n,p)$.In each round of the $(1 : q)$ Waiter-Client Hamiltonicity game, the firstplayer, called Waiter, offers the second player, called Client, $q+1$ edges of${\mathcal G}(n,p)$ which have not been offered previously. Client then choosesone of these edges, which he claims, and the remaining $q$ edges go back toWaiter. Waiter wins this game if by the time every edge of ${\mathcal G}(n,p)$has been claimed by some player, the graph consisting of Client's edges isHamiltonian; otherwise Client is the winner. Client-Waiter games are definedanalogously, the main difference being that Client wins the game if his graphis Hamiltonian and Waiter wins otherwise. In this paper we determine a sharpthreshold for both games. Namely, for every fixed positive integer $q$, weprove that the smallest edge probability $p$ for which a.a.s. Waiter has awinning strategy for the $(1 : q)$ Waiter-Client Hamiltonicity game is $(1 +o(1)) \log n/n$, and the smallest $p$ for which a.a.s. Client has a winningstrategy for the $(1 : q)$ Client-Waiter Hamiltonicity game is $(q + 1 + o(1))\log n/n$.
展开▼
机译：我们研究两种类型的两人，无机会博弈的完美信息游戏，它们在二项式随机图$ {\ mathcal G}（n，p）$的边集上玩。在$（1：q）$的每一轮中Waiter-Client Hamiltonicity游戏，第一个玩家叫Waiter，第二个玩家叫Client，$ {\ mathcal G}（n，p）$的$ q + 1 $边，以前没有提供过。然后，客户选择他所声称的这些边沿中的一个，其余的$ q $边沿返回给Waiter。如果在某位玩家要求$ {\ mathcal G}（n，p）$的每个边时，侍者赢得了这场比赛，则由客户边组成的图形就是汉密尔顿；否则，客户就是赢家。客户-侍者游戏的定义是类似的，主要区别在于，如果客户的图形汉密尔顿式的获胜，则客户获胜，否则，服务生获胜。在本文中，我们确定两种游戏的临界阈值。即，对于每个固定的正整数$ q $，我们证明a.a.s最小的边缘概率$ p $。 Waiter对于$（1：q）$ Waiter-Client Hamiltonicity游戏的制胜策略是$（1 + o（1））\ log n / n $，以及最小的$ p $。客户对于$（1：q）$ Client-Waiter Hamiltonicity游戏具有$（q + 1 + o（1））\ log n / n $的获胜策略。
展开▼
